package com.bruce.algorithm.sort;

import java.util.Arrays;

/**
 * 计数排序
 * <br>CreateDate  2021/11/04 15:40:55
 *
 * @author luotuan
 * @version 1.0.0
 */
public class CounterSort {
    public static void main(String[] args) {
        int[] array = {1, 3, 2, 6, 8, 10, 20, 11, 9};
        sort(array, array.length);
        System.out.println(Arrays.toString(array));
    }

    private static void sort(int[] a, int n) {
        if (n <= 1) {
            return;
        }
        // 找到最大值,获取数组范围
        int max = a[0];
        for (int i = 0; i < n; i++) {
            max = a[i] > max ? a[i] : max;
        }
        // 构建计数数组，下标为[0,max]
        int[] c = new int[max + 1];
        //先默认填充0
        for (int i = 0; i < max; i++) {
            c[i] = 0;
        }
        // 填充计数数组
        for (int i = 0; i < n; i++) {
            c[a[i]]++;
        }
        // 依次累加
        for (int i = 1; i <= max; i++) {
            c[i] = c[i - 1] + c[i];
        }
        // 临时数组
        int[] d = new int[n];
        //计数
        for (int i = 0; i < n; i++) {
            // 找到a[i] 在新数组中的下标
            int index = c[a[i]] - 1;
            // 赋值
            d[index] = a[i];
            // 计数数组下标-1
            c[a[i]]--;
        }
        for (int i = 0; i < n; i++) {
            a[i] = d[i];
        }
    }
}
